1. Field of the Invention
The present invention relates to decoding apparatus for expanding coded data to data representing picture elements of a facsimile of an image for communication or display.
Facsimiles of graphic images are encoded in a variety of contexts to compress the amount of storage space or the bandwidth for communication needed for the facsimiles. In order to display the coded data, the codes must be converted to digital image information. Typical systems which have used this encoding/decoding process include facsimile machines, video workstations, electronic mail systems and storage and retrieval systems.
A digital facsimile system, in which the preferred embodiment of the present invention is implemented, is an information communication machine by which picture information is transmitted from one location to another location over a communication link such as a telephone line. Typically, in facsimile systems, a scanner generates a facsimile of a graphic image by scanning the original image, such as on a document, on a line-by-line basis, each line including a large number of picture elements. The generated facsimile is then encoded by either a one-dimensional or a two-dimensional coding scheme to compress the image data to reduce the bandwidth or transmission time required for communicating the facsimile. the compressed data is then transmitted over communication links to remote facsimile machines. The remote facsimile machine decodes the compressed data to regenerate the facsimile and reproduces the original graphic image.
One-dimensional coding schemes are based upon the correlation of picture elements along a given scan line in the horizontal direction, whereas two-dimensional coding schemes are based upon a vertical correlation between successive scan lines in addition to the horizontal correlation. Both one-dimensional and two-dimensional schemes have been standardized by the International Telegraph and Telephone Consultative Committee (CCITT). The CCITT standards set forth in Recommendations T.4 and T.6 define a standard coding scheme for Group 3 and Group 4 facsimile apparatus. The recommendations of the CCITT have established compatibility among manufacturers of facsimile equipment for communication of encoded facsimile data.
The CCITT Group 3 apparatus uses a modified Huffman (MH) coding scheme for one-dimensional coding and a modified Relative Element Address Designate (MR) coding scheme for two-dimensional coding. The CCITT Group 4 apparatus uses a modified MR (MMR) coding scheme for two-dimensional coding. The one-dimensional MH coding method uses Huffman codes for the run length of black or white picture elements (PELs).
The two-dimensional coding method encodes the picture by using not only the current line information but also the previous line information. This method is a line-by-line coding method in which the position of each changing PEL on the coding line is coded with respect to the position of a corresponding reference PEL situated on either the coding line or a reference line. Based on the relative position of changing PELs, three coding modes are defined in the CCITT standards: Pass mode, Vertical mode and Horizontal mode.
For the two-dimensional coding, the CCITT standard identified five color changing elements, a0, a1, a2, b1 and b2, which are elements whose "color" differs from that of the previous adjacent element along the same scan line. The a0 is the reference or starting element on the coding line. At the start of the coding line, a0 is set on an imaginary white changing element situated just before the first element on the line. During the coding of the coding line, the position of a0 is defined by the previous coding mode. The a1 is the next changing element to the right of a0 on the coding line. The a2 is the next changing element to the right of a1 on the coding line. The b1 is the first changing element on the reference line to the right of a0 and of the opposite color to a0. The b2 is the next changing element to the right of b1 on the reference line.
The pass mode is identified when the position of b2 lies to the left of a1. When this mode has been coded, the picture element just under b2 is regarded as the new starting picture element a0 for the next coding. However, the state where b2 occurs just above a1 is not considered as a pass mode. If it is not a pass mode and the relative distance of a1b1 is less than or equal to three, then a vertical mode is identified. The relative distance a1b1 can take on one of seven values V(0), VR(1), VR(2), VR(3), VL(1), VL(2), and VL(3), each of which is represented by a separate code word. After the vertical mode has been coded, position a1 is regarded as the new starting picture element a0 for the next coding. Also, if it is not a pass mode and the relative distance of a1b1 is greater than three, then a horizontal mode is identified. When this mode is identified, both the run-lengths a0a1 and a1a2 are coded using the code words H +M(a0a1) +M(a1a2), where M(XY) is a standard run-length code for the length X to Y. After the horizontal mode has been coded, position a2 is regarded as the new starting picture element a0 for the next coding.
2. Description of the Prior Art
Prior art systems for decoding or expanding facsimile coded data to digital pixel image information suffer such disadvantages as being slow or of complicated and expensive design. In such prior art systems, the codes received for decoding are latched on word boundaries which have no correlation to the actual variable code lengths. Therefore, a single code may be included in more than one word of digital data received by a system. Hence, the prior rat systems require complicated algorithms for isolating codes in the incoming data stream.
In addition, according to the CCITT standards, the color change elements on a reference line must be identified. In the prior art, systems for identifying the relevant color change elements in a reference line have involved full line length accumulators which are large and complex logic designs. Further, the information concerning the location of a particular color change element is derived on a pixel by pixel basis in review of the previously decoded reference line.
U.S. Pat. No. 4,533,956 invented by Fedde, entitled APPARATUS FOR CONVERTING FACSIMILE CODED DATA TO VIDEO DATA, issued Aug. 6, 1985, typifies the complicated and relatively slow systems of the prior art.